Cos'è teorema di de morgan?

Il teorema di De Morgan è un principio fondamentale nella logica proposizionale che stabilisce la relazione tra negazione e operazioni logiche come l'AND (congiunzione) e l'OR (disgiunzione). È chiamato così in onore del matematico britannico Augustus De Morgan.

Il teorema afferma che la negazione di una proposizione composta attraverso una delle operazioni logiche può essere ottenuta scambiando le operazioni e negando le singole proposizioni all'interno dell'espressione.

In particolare, ci sono due versioni del teorema di De Morgan:

  1. Il primo teorema di De Morgan: la negazione di una congiunzione di due proposizioni è equivalente alla disgiunzione delle loro negazioni. Formalmente, può essere espresso come: ¬(A ∧ B) ≡ (¬A ∨ ¬B)

  2. Il secondo teorema di De Morgan: la negazione di una disgiunzione di due proposizioni è equivalente alla congiunzione delle loro negazioni. Formalmente, può essere espresso come: ¬(A ∨ B) ≡ (¬A ∧ ¬B)

Questi teoremi forniscono una regola potente per semplificare le espressioni logiche complesse e per convertire tra diverse forme di rappresentazione delle proposizioni.

In pratica, il teorema di De Morgan può essere applicato quando si desidera negare una formula che coinvolge connettivi logici. La negazione può essere spostata all'interno delle formule e applicata alle singole proposizioni per ottenere una nuova espressione equivalente.